package com.cuz.daileetcode.bat100;

import com.cuz.hot100.Q72minDistance;

public class 编辑距离问题 {
    public static void main(String[] args) {
        System.out.println(solution1("abcfde", "abcd", 1, 2, 1));
        System.out.println(solution2("abcfde", "abcd", 1, 2, 1));
        System.out.println(Q72minDistance.minDistance1("ab", "abcd"));
    }

    public static int solution1(String str1, String str2, int add, int del, int update) {
        if (isEmptyStr(str1) && isEmptyStr(str2)) {
            return 0;
        }
        return process(str1, str2, add, del, update);
    }

    private static int process(String str1, String str2, int add, int del, int update) {
        boolean isStr1Empty = isEmptyStr(str1);
        boolean isStr2Empty = isEmptyStr(str2);
        if (isStr1Empty && isStr2Empty) {
            return 0;
        }
        if (isStr1Empty || isStr2Empty) {
            if (isStr1Empty) {
                return str2.length() * add;
            } else {
                return str1.length() * del;
            }
        }
        if (str1.equals(str2)) {
            return 0;
        }
        //str1 和 str1 减去末尾相同 这时候只需要加上末尾字符
        int addSpend = process(str1, str2.substring(0, str2.length() - 1), add, del, update) + add;
        // str1 减去末尾 和str2 相同 那么只需要删除末尾字符
        int delSpend = process(str1.substring(0, str1.length() - 1), str2, add, del, update) + del;
        //各自减去一个字符 如果末尾字符相同 那么不需要花费更新 反正需要花费更新的代价
        int updateSpend = process(str1.substring(0, str1.length() - 1), str2.substring(0, str2.length() - 1), add, del, update)
                + (str1.charAt(str1.length() - 1) == str2.charAt(str2.length() - 1) ? 0 : update);
        return Math.min(Math.min(addSpend, delSpend), updateSpend);

    }

    private static boolean isEmptyStr(String str) {
        return str == null || str.length() == 0;
    }

    public static int solution2(String str1, String str2, int add, int del, int update) {
        boolean str1EmptyFlag = isEmptyStr(str1);
        boolean str2EmptyFlag = isEmptyStr(str2);
        if (str1EmptyFlag && str2EmptyFlag) {
            return 0;
        }
        if (str1EmptyFlag || str2EmptyFlag) {
            if (str1EmptyFlag) {
                return str2.length() * add;
            } else {
                return str1.length() * del;
            }
        }
        int str1Len = str1.length();
        int str2Len = str2.length();
        int[][] dp = new int[str1Len + 1][str2Len + 1];
        //str2 为空白
        for (int i = 0; i <= str1Len; i++) {
            dp[i][0] = i * del;
        }
        //str1 为null 标记成 str2[0...i]
        for (int i = 0; i <= str2Len; i++) {
            dp[0][i] = i * add;
        }
        for (int i = 1; i <= str1Len; i++) {
            for (int j = 1; j <= str2Len; j++) {
                //更新代价
                dp[i][j] = dp[i - 1][j - 1] + (str1.charAt(i - 1) == str2.charAt(j - 1) ? 0 : 1);
                //删除 vs 更新
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + del);
                //添加 更新 删除 取最小
                dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + add);
            }
        }
        return dp[str1Len][str2Len];
    }
}
